//
// Created by ASUS on 2024/6/3/星期一.
//
#include <bits/stdc++.h>

using namespace std;

//归并排序
void Merge(vector<int> &nums, int low, int mid, int high){
	int *temp = new int[high - low];
	int t = 0;
	int i = low;
	int j = mid;
	while (i < mid || j < high){
		if (i>= mid){
			temp[t++] = nums[j++];
		}else if (j>= high){
			temp[t++] = nums[i++];
		}else{
			if (nums[i] < nums[j]){
				temp[t++] = nums[i++];
			}else{
				temp[t++] = nums[j++];
			}
		}
	}
	t = 0;
	for (int i = low; i < high; i++){
		nums[i] = temp[t++];
	}
	delete[] temp;
}

void MergeSort(vector<int>&nums, int low, int high){
	if (low+1< high){
		int mid = (low + high) / 2;
		MergeSort(nums, low, mid);
		MergeSort(nums, mid, high);
		Merge(nums, low, mid, high);
	}
//    for(int k=0;k<8;k++){
//        cout<<nums[k]<<" ";
//    }
//    cout<<endl;
}